package sort;

/**
 * 插入排序
 */
public class InsertSort {

    public static void sort(int[] arrSrc) {
        int iLen = arrSrc.length;
        if (iLen <= 1) {
            return;
        }

        //将左边作为已排序区，从第二个开始比较
        for (int i = 1; i < iLen; i++) {
            int iValue = arrSrc[i];
            //比较的坐标从他的前一位开始
            int iComparePos = i - 1;

            for (; iComparePos >= 0; iComparePos--) {
                //当发现被比较的数据大于他，则将这个被比较的位置向后移动一位
                if (arrSrc[iComparePos] > iValue) {
                    arrSrc[iComparePos + 1] = arrSrc[iComparePos];
                } else {
                    break;
                }
            }

            //将数据插入到比当前数据小的位置之后
            arrSrc[iComparePos + 1] = iValue;
        }
    }

    public static void main(String[] args) {
        int[] arrSrc = CommonUtil.createIntArray(20);
        CommonUtil.printArr(arrSrc);
        sort(arrSrc);
        CommonUtil.printArr(arrSrc);
    }

}
